#include <cstdlib>
#include <string>
#include <iostream>
#include <vector>
#include <climits>

using namespace std;


 struct ListNode {
     int val;
     ListNode* next;
     ListNode(int x) : val(x), next(NULL) {}
 };

class Solution {
public:
	void print(ListNode* head){
		while (head != NULL){
			cout << head->val << endl;
			head = head->next;
		}
	}
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		// find the length of list
		ListNode* pnode = head;
		int length = 0;
		while (pnode != NULL)
		{
			++length;
			pnode = pnode->next;
		}
		if (length == 0){
			return NULL;
		}
		if (n == length){
			ListNode* tmp = head->next;
			delete head;
			return tmp;
		}
		ListNode* fore = head, *back = head->next;
		for (int i = 1; i < length - n; ++i){
			fore = back;
			back = back->next;
		}
		fore->next = back->next;
		delete back;
		return head;
	}
};
int main(int argc, char argv){
	ListNode node1(1), node2(2), node3(3);
	Solution s;
	node1.next = &node2;
	node2.next = &node3;
	node3.next = NULL;
	s.removeNthFromEnd(&node1, 1);
	s.print(&node1);
	return 0;
}